package interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;

public class Interview_day1 {


	
	public static boolean isAnagram(String s1, String s2){
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		Arrays.sort(c1);
		Arrays.sort(c2);
		return Arrays.equals(c1, c2);
	}
	
	/**
	 * !Just as the partition function in quicksort
	 * 
	 * For an array with length n, the median is:
	 * 1) (n/2)th and (n/2+1)th for n % 2 == 0
	 * 2) ((n-1)/2) for n % 2 == 1
	 * 
	 * Pick arbitrary number i
	 * Let all number > i be placed on the right side of i,
	 * and all number < i be placed on the left side of i
	 * Num(right) = q, Num(left) = p, p+q+1 = n;
	 * 
	 * for n % 2 == 1
	 * if p > q, in left, the ((n-1)/2)
	 * if q > p, in right, the ((n-1)/2) - p
	 * 
	 * for n % 2 == 0
	 * if |p - q| = 1, i is one of the median
	 * else.....
	 * 
	 * @param a
	 * @param start
	 * @param end
	 * @param mpos
	 * @return
	 */
	public static int findMedian(int[] a){
		if(a == null) return Integer.MIN_VALUE;
		if(a.length % 2 == 1) return randomSelect(a, 0, a.length-1, (int)a.length/2);
		else return (randomSelect(a, 0, a.length-1, (int)a.length/2-1) + randomSelect(a, 0, a.length-1, (int)a.length/2))/2;
	}
	
	public static int randomSelect(int[] a, int start, int end, int order){
		if(start == end) 
			return a[start];
		else{
			//random partition
			Random r = new Random();
			int temp  = r.nextInt(end-start+1) + start;
			//exchange a[temp] & a[end]
			a[temp] = a[temp]^a[end];
			a[end] = a[temp]^a[end];
			a[temp] = a[temp]^a[end];
			//partition
			int q = start;
			for(int i = start ; i < end ; i++){
				if(a[i] < a[end] && i!= q){//notice, using this method of swap, i and q couldn't be the same
					a[i] = a[q] ^ a[i];
					a[q] = a[q] ^ a[i];
					a[i] = a[q] ^ a[i];
					q++;
				}
			}
			a[end] = a[q] ^ a[end];
			a[q] = a[q] ^ a[end];
			a[end] = a[q] ^ a[end];//end random partition
			
			int k = q-start+1;
			if(k == order) return a[q];
			else if(k > order) return randomSelect(a, start, q-1, order);
			else return randomSelect(a, q+1, end, order-k);
		}
	}
	
	/**
	 * Method:
	 * when calculation pow(x,y) % z without pow
	 * if x^y is very huge, we cannot calculate x^y first becasue it leads to overflow.
	 * so, we use this: x^y%z = (x^(y1)%z) * (x^(y2)%z) % z
	 * @param x
	 * @param y
	 * @param z
	 * @return
	 */
	public static int calculateXpowYmodZwithoutPow(int x, int y, int z){
		if(z == 0 || y < 0) return -1;
		if(y == 1) return x%z;
		if(y == 0) return 1%z;
		else{
			int y1 = y/2;
			int y2 = y - y1;
			return calculateXpowYmodZwithoutPow(x, y1, z) * calculateXpowYmodZwithoutPow(x, y2, z) % z;
		}
	}
	
	/**
	 * !You are given two array, first array contain integer 
	 * which represent heights of persons and second array contain how many persons 
	 * in front of him are standing who are greater than him 
	 * in term of height and forming a queue. Ex 
	 * A: 3 2 1 
	 * B: 0 1 1 
	 * It means in front of person of height 3 there is no person standing, 
	 * person of height 2 there is one person in front of him who has greater height then he, 
	 * similar to person of height 1. Your task to arrange them 
	 * Ouput should be. 
	 * 3 1 2 
	 * Here - 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front
	 * 
	 * Notice: This problem can be translated to reconstructing permutation from an inversion sequence.
	 * we know a permutation: 
	 * a[] 2 4 5 1 7 6 3 8
	 * when compared to 1 2 3 4 5 6 7 8
	 * the inversion sequence is:
	 * b[] = 0 1 0 2 2 1 2 0
	 * the ith of this sequence is the number of numbers j that are strictly less than i
	 * when i = 1, b[1] = 0 because, there is no number on the right of a[4] is less than 1
	 * when i = 2, b[2] = 1 because there is one number on the right of a[1] is less than 2 
	 * 
	 * Method:
	 * sort the array A with descending order
	 */
	public static void arrangeQueueOfPeople(int[] p, int[] pre){
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		for(int i = 0 ; i < p.length ; i++) hm.put(i, p[i]);
		
		List<Entry<Integer, Integer>> pp = new LinkedList<Entry<Integer, Integer>>();
		pp.addAll(hm.entrySet());
		Collections.sort(pp, new Comparator<Entry<Integer, Integer>>(){
			@Override
			public int compare(Entry<Integer, Integer> o1,
					Entry<Integer, Integer> o2) {
				return o2.getValue() - o1.getValue();
			}
			
		}); 
		hm = new HashMap<Integer, Integer>();
		for(int i = 0 ; i < pp.size() ; i++){
			Entry<Integer, Integer> e = pp.get(i);
			hm.put(i, pre[i]-i);
		}
		
		for(int i = 0 ; i < pp.size() ; i++){
			int bias = hm.get(i);
			if(bias == 0) continue;
			int val = pp.get(i).getValue();
			if(bias > 0){//find bias number of people higher than i
				//and move them backward
				int ind = i-1; 
				int[] indexes = new int[bias];
				for(int j = bias-1 ; j >= 0 ; j--)
					if(pp.get(ind).getValue() > val) {
						indexes[j] = ind;
						ind--;
					}
				for(int j = 0 ; j < bias ; j++){
					Entry<Integer, Integer> e = pp.get(indexes[j]);
					pp.remove(pp.get(indexes[j]));
					pp.add(i, e);
				}
			}else{//move i forward
				
			}
			hm.put(i, 0);
		}
	}
	
	/**
	 * Delete the repeated elements in a singly linked list 
	 * in O(n) time complexity without using extra space. 
	 * Linked list contains elements in unsorted order 
	 * P.S. - Sorting is not allowed
	 * @param head
	 */
	public static void removeDuplicatesFromLinkedList(ListNode head){
		ListNode pre = head, cur = head.next;
		while(cur != null){
			if(pre.val == cur.val){//remove cur
				pre.next = cur.next;
				cur = pre.next;
			}else{
				pre = cur;
				cur = cur.next;
			}
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(findMedian(new int[]{3,4,1,8,6,9,0}));
		System.out.println(calculateXpowYmodZwithoutPow(100,10000,11));
	}

}

class ListNode<T>{
	public T val;
	public ListNode<T> next;
	
	public ListNode(T val){
		this.val = val;
	}
}
